home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 25 / CU Amiga Magazine's Super CD-ROM 25 (1998)(EMAP Images)(GB)(Track 1 of 2)[!][issue 1998-08].iso / CUCD / Programming / QuakeTools / src / libqbuild / winding.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-06-11  |  12.8 KB  |  582 lines
  1. #define    LIBQBUILD_CORE
  2. #include "../include/libqbuild.h"
  3.  
  4. int c_activewindings, c_peakwindings;
  5.  
  6. //===========================================================================
  7.  
  8. void WindingBounds(register struct winding *w, vec3_t mins, vec3_t maxs)
  9. {
  10.   vec_t v;
  11.   int i, j;
  12.  
  13.   mins[0] = mins[1] = mins[2] = 99999;
  14.   maxs[0] = maxs[1] = maxs[2] = -99999;
  15.  
  16.   for (i = 0; i < w->numpoints; i++) {
  17.     for (j = 0; j < 3; j++) {
  18.       v = w->points[i][j];
  19.       if (v < mins[j])
  20.     mins[j] = v;
  21.       if (v > maxs[j])
  22.     maxs[j] = v;
  23.     }
  24.   }
  25. }
  26. void WindingCenter(register struct winding *w, vec3_t center)
  27. {
  28.   int i;
  29.  
  30.   VectorClear(center);
  31.   for (i = 0; i < w->numpoints; i++)
  32.     VectorAdd(w->points[i], center, center);
  33.  
  34.   VectorScale(center, 1.0 / w->numpoints, center);
  35. }
  36.  
  37. vec_t WindingArea(register struct winding *w)
  38. {
  39.   int i;
  40.   vec3_t d1, d2, cross;
  41.   vec_t total = 0;
  42.  
  43.   for (i = 2; i < w->numpoints; i++) {
  44.     VectorSubtract(w->points[i - 1], w->points[0], d1);
  45.     VectorSubtract(w->points[i], w->points[0], d2);
  46.     CrossProduct(d1, d2, cross);
  47.     total += 0.5 * VectorLength(cross);
  48.   }
  49.   return total;
  50. }
  51.  
  52. /*
  53.  * =================
  54.  * BaseWindingForPlane
  55.  * =================
  56.  */
  57. struct winding *BaseWindingForPlane(register struct plane *p)
  58. {
  59.   int i, x;
  60.   vec_t max, v;
  61.   vec3_t org, vright, vup;
  62.   struct winding *w;
  63.  
  64. // find the major axis
  65.  
  66.   max = -BOGUS_RANGE;
  67.   x = -1;
  68.   for (i = 0; i < 3; i++) {
  69.     v = fabs(p->normal[i]);
  70.     if (v > max) {
  71.       x = i;
  72.       max = v;
  73.     }
  74.   }
  75.   if (x == -1)
  76.     Error("BaseWindingForPlane: no axis found");
  77.  
  78.   VectorClear(vup);
  79.   switch (x) {
  80.     case 0:
  81.     case 1:
  82.       vup[2] = 1;
  83.       break;
  84.     case 2:
  85.       vup[0] = 1;
  86.       break;
  87.   }
  88.  
  89.   v = DotProduct(vup, p->normal);
  90.   VectorMA(vup, -v, p->normal, vup);
  91.   VectorNormalize(vup);
  92.  
  93.   VectorScale(p->normal, p->dist, org);
  94.  
  95.   CrossProduct(vup, p->normal, vright);
  96.  
  97.   VectorScale(vup, 8192, vup);
  98.   VectorScale(vright, 8192, vright);
  99.  
  100. // project a really big axis aligned box onto the plane
  101.   w = NewWinding(4);
  102.  
  103.   VectorSubtract(org, vright, w->points[0]);
  104.   VectorAdd(w->points[0], vup, w->points[0]);
  105.  
  106.   VectorAdd(org, vright, w->points[1]);
  107.   VectorAdd(w->points[1], vup, w->points[1]);
  108.  
  109.   VectorAdd(org, vright, w->points[2]);
  110.   VectorSubtract(w->points[2], vup, w->points[2]);
  111.  
  112.   VectorSubtract(org, vright, w->points[3]);
  113.   VectorSubtract(w->points[3], vup, w->points[3]);
  114.  
  115.   w->numpoints = 4;
  116.  
  117.   return w;
  118. }
  119.  
  120. /*
  121.  * =============
  122.  * WindingFromFace
  123.  * =============
  124.  */
  125. struct winding *WindingFromFace(__memBase, register struct dface_t *f)
  126. {
  127.   int se;
  128.   struct dvertex_t *dv;
  129.   int v;
  130.   struct winding *w;
  131.   int i, j, k;
  132.   vec3_t v1, v2;
  133.   int nump;
  134.   vec3_t p[MAX_POINTS_ON_WINDING];
  135.  
  136.   w = NewWinding(f->numedges);
  137.   w->numpoints = f->numedges;
  138.  
  139.   for (i = 0; i < f->numedges; i++) {
  140.     se = bspMem->dsurfedges[f->firstedge + i];
  141.     if (se < 0)
  142.       v = bspMem->dedges[-se].v[1];
  143.     else
  144.       v = bspMem->dedges[se].v[0];
  145.  
  146.     dv = &bspMem->dvertexes[v];
  147.     VectorCopy(dv->point, w->points[i]);
  148.   }
  149.  
  150.   nump = 0;
  151.   for (i = 0; i < w->numpoints; i++) {
  152.     j = (i + 1) % w->numpoints;
  153.     k = (i + w->numpoints - 1) % w->numpoints;
  154.     VectorSubtract(w->points[j], w->points[i], v1);
  155.     VectorSubtract(w->points[i], w->points[k], v2);
  156.     VectorNormalize(v1);
  157.     VectorNormalize(v2);
  158.     if (DotProduct(v1, v2) < 0.999) {
  159.       VectorCopy(w->points[i], p[nump]);
  160.       nump++;
  161.     }
  162.   }
  163.  
  164.   if (nump != w->numpoints) {
  165.     w->numpoints = nump;
  166.     memcpy(w->points, p, nump * sizeof(vec3_t));
  167.   }
  168.   return w;
  169. }
  170.  
  171. /*
  172.  * ==================
  173.  * CopyWinding
  174.  * ==================
  175.  */
  176. struct winding *CopyWinding(register struct winding *w)
  177. {
  178.   int size;
  179.   struct winding *c;
  180.  
  181.   size = (int)((struct winding *)0)->points[w->numpoints];
  182.   if (!(c = (struct winding *)tmalloc(size)))
  183.     Error("CopyWinding: failed to allocate winding!\n");
  184.   memcpy(c, w, size);
  185.   c->original = FALSE;
  186.   return c;
  187. }
  188.  
  189. /*
  190.  * ==================
  191.  * CheckWinding
  192.  * 
  193.  * Check for possible errors
  194.  * ==================
  195.  */
  196. void CheckWinding(register struct winding *w)
  197. {
  198. }
  199.  
  200. void CheckWindingInNode(register struct winding *w, register struct node *node)
  201. {
  202.   int i, j;
  203.  
  204.   for (i = 0; i < w->numpoints; i++) {
  205.     for (j = 0; j < 3; j++)
  206.       if (w->points[i][j] < node->mins[j] - 1
  207.       || w->points[i][j] > node->maxs[j] + 1) {
  208.     eprintf("CheckWindingInNode: outside\n");
  209.     return;
  210.       }
  211.   }
  212. }
  213.  
  214. void CheckWindingArea(register struct winding *w)
  215. {
  216.   int i;
  217.   float total, add;
  218.   vec3_t v1, v2, cross;
  219.  
  220.   total = 0;
  221.   for (i = 1; i < w->numpoints; i++) {
  222.     VectorSubtract(w->points[i], w->points[0], v1);
  223.     VectorSubtract(w->points[i + 1], w->points[0], v2);
  224.     CrossProduct(v1, v2, cross);
  225.     add = VectorLength(cross);
  226.     total += add * 0.5;
  227.   }
  228.   if (total < 16)
  229.     eprintf("winding area %f\n", total);
  230. }
  231.  
  232. void PlaneFromWinding(register struct winding *w, register struct plane *plane)
  233. {
  234.   vec3_t v1, v2;
  235.  
  236. // calc plane
  237.   VectorSubtract(w->points[2], w->points[1], v1);
  238.   VectorSubtract(w->points[0], w->points[1], v2);
  239.   CrossProduct(v2, v1, plane->normal);
  240.   VectorNormalize(plane->normal);
  241.   plane->dist = DotProduct(w->points[0], plane->normal);
  242. }
  243.  
  244. /*
  245.  * ==================
  246.  * ClipWinding
  247.  * 
  248.  * Clips the winding to the plane, returning the new winding on the positive side
  249.  * Frees the input winding.
  250.  * If keepon is TRUE, an exactly on-plane winding will be saved, otherwise
  251.  * it will be clipped away.
  252.  * ==================
  253.  */
  254. struct winding *ClipWinding(register struct winding *in, register struct plane *split, register bool keepon)
  255. {
  256.   vec_t dists[MAX_POINTS_ON_WINDING];
  257.   int sides[MAX_POINTS_ON_WINDING];
  258.   int counts[3];
  259.   vec_t dot;
  260.   int i, j;
  261.   vec_t *p1, *p2;
  262.   vec3_t mid;
  263.   struct winding *neww;
  264.   int maxpts;
  265.  
  266.   counts[0] = counts[1] = counts[2] = 0;
  267.  
  268. // determine sides for each point
  269.   for (i = 0; i < in->numpoints; i++) {
  270.     dot = DotProduct(in->points[i], split->normal);
  271.     dot -= split->dist;
  272.     dists[i] = dot;
  273.     if (dot > ON_EPSILON)
  274.       sides[i] = SIDE_FRONT;
  275.     else if (dot < -ON_EPSILON)
  276.       sides[i] = SIDE_BACK;
  277.     else {
  278.       sides[i] = SIDE_ON;
  279.     }
  280.     counts[sides[i]]++;
  281.   }
  282.   sides[i] = sides[0];
  283.   dists[i] = dists[0];
  284.  
  285. /*
  286.  * printf("counts[0]: %d\n", counts[0]);
  287.  * printf("counts[1]: %d\n", counts[1]);
  288.  */
  289.  
  290.   if (keepon && !counts[0] && !counts[1])
  291.     return in;
  292.  
  293.   if (!counts[0]) {
  294.     FreeWinding(in);
  295.     return NULL;
  296.   }
  297.   if (!counts[1])
  298.     return in;
  299.  
  300.   maxpts = in->numpoints + 4;                               // can't use counts[0]+2 because
  301.   // of fp grouping errors
  302.  
  303.   neww = NewWinding(maxpts);
  304.  
  305.   for (i = 0; i < in->numpoints; i++) {
  306.     p1 = in->points[i];
  307.  
  308.     if (sides[i] == SIDE_ON) {
  309.       VectorCopy(p1, neww->points[neww->numpoints]);
  310.       neww->numpoints++;
  311.       continue;
  312.     }
  313.  
  314.     if (sides[i] == SIDE_FRONT) {
  315.       VectorCopy(p1, neww->points[neww->numpoints]);
  316.       neww->numpoints++;
  317.     }
  318.  
  319.     if (sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i])
  320.       continue;
  321.  
  322.     // generate a split point
  323.     p2 = in->points[(i + 1) % in->numpoints];
  324.  
  325.     dot = dists[i] / (dists[i] - dists[i + 1]);
  326.     for (j = 0; j < 3; j++) {                               // avoid round off error when possible
  327.  
  328.       if (split->normal[j] == 1)
  329.     mid[j] = split->dist;
  330.       else if (split->normal[j] == -1)
  331.     mid[j] = -split->dist;
  332.       else
  333.     mid[j] = p1[j] + dot * (p2[j] - p1[j]);
  334.     }
  335.  
  336.     VectorCopy(mid, neww->points[neww->numpoints]);
  337.     neww->numpoints++;
  338.   }
  339.  
  340.   if (neww->numpoints > maxpts)
  341.     Error("ClipWinding: points exceeded estimate");
  342.  
  343. // free the original winding
  344.   FreeWinding(in);
  345.  
  346.   return neww;
  347. }
  348.  
  349. void ClipWindingEpsilon(struct winding *in, vec3_t normal, vec_t dist,
  350.             vec_t epsilon, struct winding **front, struct winding **back)
  351. {
  352.   vec_t dists[MAX_POINTS_ON_WINDING + 4];
  353.   int sides[MAX_POINTS_ON_WINDING + 4];
  354.   int counts[3];
  355.   vec_t dot;
  356.   int i, j;
  357.   vec_t *p1, *p2;
  358.   vec3_t mid;
  359.   struct winding *f, *b;
  360.   int maxpts;
  361.  
  362.   counts[0] = counts[1] = counts[2] = 0;
  363.  
  364. // determine sides for each point
  365.   for (i = 0; i < in->numpoints; i++) {
  366.     dot = DotProduct(in->points[i], normal);
  367.     dot -= dist;
  368.     dists[i] = dot;
  369.     if (dot > epsilon)
  370.       sides[i] = SIDE_FRONT;
  371.     else if (dot < -epsilon)
  372.       sides[i] = SIDE_BACK;
  373.     else {
  374.       sides[i] = SIDE_ON;
  375.     }
  376.     counts[sides[i]]++;
  377.   }
  378.   sides[i] = sides[0];
  379.   dists[i] = dists[0];
  380.  
  381.   *front = *back = NULL;
  382.  
  383.   if (!counts[0]) {
  384.     *back = CopyWinding(in);
  385.     return;
  386.   }
  387.   if (!counts[1]) {
  388.     *front = CopyWinding(in);
  389.     return;
  390.   }
  391.  
  392.   maxpts = in->numpoints + 4;                               // cant use counts[0]+2 because
  393.   // of fp grouping errors
  394.  
  395.   *front = f = NewWinding(maxpts);
  396.   *back = b = NewWinding(maxpts);
  397.  
  398.   for (i = 0; i < in->numpoints; i++) {
  399.     p1 = in->points[i];
  400.  
  401.     if (sides[i] == SIDE_ON) {
  402.       VectorCopy(p1, f->points[f->numpoints]);
  403.       f->numpoints++;
  404.       VectorCopy(p1, b->points[b->numpoints]);
  405.       b->numpoints++;
  406.       continue;
  407.     }
  408.  
  409.     if (sides[i] == SIDE_FRONT) {
  410.       VectorCopy(p1, f->points[f->numpoints]);
  411.       f->numpoints++;
  412.     }
  413.     if (sides[i] == SIDE_BACK) {
  414.       VectorCopy(p1, b->points[b->numpoints]);
  415.       b->numpoints++;
  416.     }
  417.  
  418.     if (sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i])
  419.       continue;
  420.  
  421.     // generate a split point
  422.     p2 = in->points[(i + 1) % in->numpoints];
  423.  
  424.     dot = dists[i] / (dists[i] - dists[i + 1]);
  425.     for (j = 0; j < 3; j++) {                               // avoid round off error when possible
  426.  
  427.       if (normal[j] == 1)
  428.     mid[j] = dist;
  429.       else if (normal[j] == -1)
  430.     mid[j] = -dist;
  431.       else
  432.     mid[j] = p1[j] + dot * (p2[j] - p1[j]);
  433.     }
  434.  
  435.     VectorCopy(mid, f->points[f->numpoints]);
  436.     f->numpoints++;
  437.     VectorCopy(mid, b->points[b->numpoints]);
  438.     b->numpoints++;
  439.   }
  440.  
  441.   if (f->numpoints > maxpts || b->numpoints > maxpts)
  442.     Error("ClipWinding: points exceeded estimate");
  443.   if (f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING)
  444.     Error("ClipWinding: MAX_POINTS_ON_WINDING");
  445. }
  446. /*
  447.  * ==================
  448.  * DivideWinding
  449.  * 
  450.  * Divides a winding by a plane, producing one or two windings.  The
  451.  * original winding is not damaged or freed.  If only on one side, the
  452.  * returned winding will be the input winding.  If on both sides, two
  453.  * new windings will be created.
  454.  * ==================
  455.  */
  456. void DivideWinding(struct winding *in, struct plane *split, struct winding **front, struct winding **back)
  457. {
  458.   vec_t dists[MAX_POINTS_ON_WINDING];
  459.   int sides[MAX_POINTS_ON_WINDING];
  460.   int counts[3];
  461.   vec_t dot;
  462.   int i, j;
  463.   vec_t *p1, *p2;
  464.   vec3_t mid;
  465.   struct winding *f, *b;
  466.   int maxpts;
  467.  
  468.   counts[0] = counts[1] = counts[2] = 0;
  469.  
  470. // determine sides for each point
  471.   for (i = 0; i < in->numpoints; i++) {
  472.     dot = DotProduct(in->points[i], split->normal);
  473.     dot -= split->dist;
  474.     dists[i] = dot;
  475.     if (dot > ON_EPSILON)
  476.       sides[i] = SIDE_FRONT;
  477.     else if (dot < -ON_EPSILON)
  478.       sides[i] = SIDE_BACK;
  479.     else {
  480.       sides[i] = SIDE_ON;
  481.     }
  482.     counts[sides[i]]++;
  483.   }
  484.   sides[i] = sides[0];
  485.   dists[i] = dists[0];
  486.  
  487.   *front = *back = NULL;
  488.  
  489.   if (!counts[0]) {
  490.     *back = in;
  491.     return;
  492.   }
  493.   if (!counts[1]) {
  494.     *front = in;
  495.     return;
  496.   }
  497.  
  498.   maxpts = in->numpoints + 4;                               // can't use counts[0]+2 because
  499.   // of fp grouping errors
  500.  
  501.   *front = f = NewWinding(maxpts);
  502.   *back = b = NewWinding(maxpts);
  503.  
  504.   for (i = 0; i < in->numpoints; i++) {
  505.     p1 = in->points[i];
  506.  
  507.     if (sides[i] == SIDE_ON) {
  508.       VectorCopy(p1, f->points[f->numpoints]);
  509.       f->numpoints++;
  510.       VectorCopy(p1, b->points[b->numpoints]);
  511.       b->numpoints++;
  512.       continue;
  513.     }
  514.  
  515.     if (sides[i] == SIDE_FRONT) {
  516.       VectorCopy(p1, f->points[f->numpoints]);
  517.       f->numpoints++;
  518.     }
  519.     if (sides[i] == SIDE_BACK) {
  520.       VectorCopy(p1, b->points[b->numpoints]);
  521.       b->numpoints++;
  522.     }
  523.  
  524.     if (sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i])
  525.       continue;
  526.  
  527.     // generate a split point
  528.     p2 = in->points[(i + 1) % in->numpoints];
  529.  
  530.     dot = dists[i] / (dists[i] - dists[i + 1]);
  531.     for (j = 0; j < 3; j++) {                               // avoid round off error when possible
  532.  
  533.       if (split->normal[j] == 1)
  534.     mid[j] = split->dist;
  535.       else if (split->normal[j] == -1)
  536.     mid[j] = -split->dist;
  537.       else
  538.     mid[j] = p1[j] + dot * (p2[j] - p1[j]);
  539.     }
  540.  
  541.     VectorCopy(mid, f->points[f->numpoints]);
  542.     f->numpoints++;
  543.     VectorCopy(mid, b->points[b->numpoints]);
  544.     b->numpoints++;
  545.   }
  546.  
  547.   if (f->numpoints > maxpts || b->numpoints > maxpts)
  548.     Error("ClipWinding: points exceeded estimate");
  549. }
  550.  
  551. /*
  552.  * ==================
  553.  * NewWinding
  554.  * ==================
  555.  */
  556. struct winding *NewWinding(register int points)
  557. {
  558.   struct winding *w;
  559.   int size;
  560.  
  561.   if (points > MAX_POINTS_ON_WINDING)
  562.     Error("NewWinding: %i points", points);
  563.  
  564.   c_activewindings++;
  565.   if (c_activewindings > c_peakwindings)
  566.     c_peakwindings = c_activewindings;
  567.  
  568.   size = (int)((struct winding *)0)->points[points];
  569.   if (!(w = (struct winding *)tmalloc(size)))
  570.     Error("NewWinding: failed to allocate winding!\n");
  571.   memset(w, 0, size);
  572.  
  573.   return w;
  574. }
  575.  
  576. void FreeWinding(register struct winding *w)
  577. {
  578.   c_activewindings--;
  579.   if (w->original == FALSE)
  580.     tfree(w);
  581. }
  582.